1043. Can you answer these queries - 1

 

You are given an integer sequence a1, a2, ..., an (|ai| ≤ 15007, 1 ≤ n ≤ 50000). A query is defined as follows:

Query(x, y) = MAX {ai + ai+1 + ... + aj, x ≤ i ≤ j ≤ y}

Given m queries, your program must output the results of these queries.

 

Input. The first line contains the integer n. In the second line n integers of the sequence are given. The third line contains the integer m. Then m lines follow, where line i contains two numbers xi and yi.

 

Output. Print the results of the m queries, one query per line.

 

Sample input

3

-1 2 3

1

1 2

 

Sample output

2

 

 

РЕШЕНИЕ

структуры данных – дерево отрезков

 

Анализ алгоритма

Для решения задачи следует реализовать нетривиальное обобщение дерева отрезков. В каждой его вершине будем хранить четыре величины: сумму summa на этом отрезке, максимальную сумму prefix среди всех префиксов этого отрезка, максимальную сумму suffix среди всех суффиксов, а также максимальную сумму max подотрезка на нём. То есть для каждого отрезка ответ будет предпосчитан не только для него, но и для отрезков, упирающихся в его левую и правую границы.

Пусть отрезок [a..b] соответствует вершине дерева. Пусть левый его сын содержит информацию по отрезку [a..m], а правый – по [m+1..b]. Тогда значения величин в корне пересчитываются через значения величин в сыновьях следующим образом:

prefix[a..b] = max(prefix[a..m], summa[a..m] + prefix[m+1..b])

 suffix[a..b] = max(suffix[m+1..b], suffix[a..m] + summa[m+1..b])

max[a..b] = max(max[a..m], max[m+1..b], suffix[a..m] + prefix[m+1..b])

summa[a..b] = summa[a..m] + summa[m+1..b]

Например, исходя из приведенных равенств, максимальная сумма на отрезке может равняться одному из следующих значений:

·         максимуму на отрезке левого сына (лучший подотрезок в текущей вершине целиком помещается в отрезок левого сына);

·         максимуму на отрезке правого сына (лучший подотрезок в текущей вершине целиком помещается в отрезок правого сына);

·         сумме максимального суффикса в левом сыне и максимального префикса в правом сыне (лучший подотрезок лежит своим началом в левом сыне, а концом в правом)

 

Пример

Пусть некоторая вершина дерева соответствует отрезку [0..5]:

 Тогда дополнительные величины, хранящиеся в ней, имеют следующие значения:

 

Пусть указанная вершина имеет левого [0..2] и правого [3..5] сына, дополнительные значения в которых имеют значения:

 

                                                             

 

                             

                            

                            

                         

 

При объединении отрезков [0..2] и [3..5] дополнительные значения пересчитываются следующим образом:

prefix[0..5] = max(prefix[0..2], summa[0..2] + prefix[3..5]) = max (2, 0 + 3) = 3

suffix[0..5] = max(suffix[3..5], suffix[0..2] + summa[3..5]) = max (1, 2 – 3) = 1

max[0..5] = max(max[0..2], max[3..5], suffix[0..2] + prefix[3..5]) = max (4, 3, 2 2 + 3) = 5

summa[0..5] = summa[0..2] + summa[3..5] = 0 – 3 = -3

 

Реализация алгоритма

 

#include <cstdio>

#include <algorithm>

#define MAX 50100

using namespace std;

 

struct node

{

  int summa, prefix, suffix, max;

} SegTree[4*MAX];

 

int mas[MAX];

 

node Merge(node &Left, node &Right)

{

  node Res;

  Res.prefix = max(Left.prefix,Left.summa + Right.prefix);

  Res.suffix = max(Right.suffix,Right.summa + Left.suffix);

  Res.summa = Left.summa + Right.summa;

  Res.max = max(max(Left.max,Right.max),Left.suffix + Right.prefix);

  return Res;

}

 

void build(int *a, int Vertex, int LeftPos, int RightPos)

{

  if (LeftPos == RightPos)

  {

    SegTree[Vertex].max = SegTree[Vertex].prefix =

    SegTree[Vertex].suffix = SegTree[Vertex].summa = a[LeftPos];

  }

  else

  {

    int Middle = (LeftPos + RightPos) / 2;

    build (a, 2*Vertex, LeftPos, Middle);

    build (a, 2*Vertex+1, Middle+1, RightPos);

 

    SegTree[Vertex] = Merge(SegTree[2*Vertex], SegTree[2*Vertex+1]);

  }

}

 

struct node GetMax(int Vertex, int LeftPos, int RightPos,

                   int Left, int Right)

{

  if ((Left == LeftPos) && (Right == RightPos)) return SegTree[Vertex];

  int Middle = (LeftPos + RightPos) / 2;

 

  if (Right <= Middle ) return GetMax(2*Vertex,LeftPos, Middle,Left,Right);

  if (Left > Middle) return GetMax(2*Vertex+1,Middle+1,RightPos,Left,Right);

 

  struct node LeftNode  =

         GetMax(2*Vertex,LeftPos,Middle,Left,Middle);

  struct node RightNode =

         GetMax(2*Vertex+1,Middle+1,RightPos,Middle+1,Right);

 

  return Merge(LeftNode, RightNode);

}

 

int i, L, R, n, m;

struct node res;

 

int main(void)

{

  scanf("%d",&n);

  for(i = 0; i < n; i++)

    scanf("%d",&mas[i]);

 

  build(mas,1,0,n-1);

 

  scanf("%d",&m);

  for(i = 0; i < m; i++)

  {

    scanf("%d %d",&L,&R);

    res = GetMax(1,0,n-1,L-1,R-1);

    printf("%d\n",res.max);

  }

  return 0;

}